package com.example.lcpractice.lc;


import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * [215]数组中的第K个最大元素.java
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * <p>
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * <p>
 * 示例 1:
 * <p>
 * 输入:
 * [3,2,1,5,6,4],
 * k = 2
 * 输出: 5
 * 示例 2:
 * <p>
 * 输入:
 * [3,2,3,1,2,4,5,5,6],
 * k = 4
 * 输出: 4
 * 提示：
 * <p>
 * 1 <= k <= nums.length <= 105
 * -104 <= nums[i] <= 104
 * Related Topics
 * 数组
 * 分治
 * 快速选择
 * 排序
 * 堆（优先队列
 */
public class Lc215 {


    public static void main(String[] args) {
        int[] nums = {7, 8, 1, 4, 99};
        System.out.println(findKthLargest2(nums, 2));
    }

    public static int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }

    // 桶排序（推荐）
    public static int findKthLargest2(int[] nums, int k) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            max = Math.max(max, num);
            min = Math.min(min, num);
        }
        int[] bucket = new int[max - min + 1];
        for (int i = 0; i < nums.length; i++) {
            bucket[nums[i] - min]++;
        }
        int count = 0;
        for (int j = bucket.length - 1; j >= 0; j--) {
            count += bucket[j];
            if (count >= k) {
                return j + min;
            }
        }

        return -1;
    }

    //    堆排序,java中的PriorityQueue即是二叉小顶堆来实现的，自己实现一个小顶堆太麻烦，可以借用java的PriortyQueue来实现：
    public static int findKthLargest3(int[] nums, int k) {
        Queue<Integer> queue = new PriorityQueue<>();
        for (int num : nums) {
            queue.add(num);
            //当queue的大小大于k，每次弹出堆顶的最小元素；
            if (queue.size() > k) {
                queue.poll();
            }
        }
        return queue.peek();
    }

    // 第k大元素的快排后索引位置；
    static int kk;

    public int findKthLargest4(int[] nums, int k) {
        kk = nums.length - k;
        quickSort(nums, 0, nums.length-1);
        return nums[kk];
    }

    private void quickSort(int[] data, int start, int end){
        if(start < end){
            int mid = partition(data, start,end);
            //当第k大位置的数字归位时，结束递归遍历；
            if(mid == kk) return;
            else if(mid > kk) quickSort(data, start, mid-1);
            else quickSort(data, mid+1, end);

        }
    }

    private int partition(int[] data, int start, int end ){
        int key = data[start];
        if(start > end) return -1;
        while(start < end){
            //一定要从后往前遍历！
            while(start < end && data[end] >= key) {
                end--;
            }
            if(start < end) {
                swap(data, start, end);
            }
            while(start < end && data[start] <= key) {
                start++;
            }
            if(start < end) {
                swap(data, start, end);
            }
        }

        return start;
    }

    private void swap(int[] data, int i, int j){
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
}
